package com.company.Sort;

/**
 * Created by v on 16-12-11.
 */
public class QuickSelect {
    //不允许创建对象
    private QuickSelect(){};

    //判定是否是用插入排序的常数
    private static final int CUTOFF=10;

    public static<E extends Comparable<E>> E quickSelect(E[] array,int k){
        quickSelect(array,0,array.length-1,k);

        return array[k-1];
    }

    private static <E extends Comparable<E>> void quickSelect
            (E[] array,int left,int right,int k){
        if(left+CUTOFF>right){
            insertionSort(array,left,right);
            return;
        }

        E pivot=median3(array,left,right);

        int i=left;
        int j=right-1;

        while (true){
            while (array[++i].compareTo(pivot)<0);
            while (array[--j].compareTo(pivot)>0);

            if(j>i){
                swapReferences(array,i,j);
            }else {
                break;
            }
        }

        swapReferences(array,i,right-1);

        if(i>k-1){
            quickSelect(array,left,i-1,k);
        }else if(i<k-1){
            quickSelect(array,i+1,right,k);
        }else {
            return;
        }
    }

    //对过于小的数组实行插入排序，一个是防止最坏情况的产生，一个是能有效的增加效率
    private static <E extends Comparable<E>> void insertionSort
    (E[] array,int left,int right){
        for(int i=left+1;i<=right;i++){
            E temp=array[i];

            int j;
            for(j=i;j>left&&temp.compareTo(array[j-1])<0
                    ;j--){
                array[j]=array[j-1];
            }

            array[j]=temp;
        }
    }

    //该方法用于交换数组中的两个位点的值
    private final static <E extends Comparable<E>> void swapReferences
            (E[] array,int left,int right){
        E temp=array[left];
        array[left]=array[right];
        array[right]=temp;
    }

    //寻找快速排序的枢纽元,三数中值分割法,返回枢纽元
    private static <E extends Comparable<E>> E median3
    (E[] array,int left,int right){
        int center=(left+right)/2;

        if(array[center].compareTo(array[left])<0){
            swapReferences(array,center,left);
        }

        if(array[right].compareTo(array[left])<0){
            swapReferences(array,right,left);
        }

        if(array[right].compareTo(array[center])<0){
            swapReferences(array,right,center);
        }

        //把枢纽元放在right-1处
        swapReferences(array,center,right-1);

        return array[right-1];
    }
}
